package com.wfm.leetcode.editor.cn;

import org.junit.Test;

import java.util.ArrayList;
import java.util.HashMap;
import java.util.List;

/**
 * 逐个遍历每个字符，第一次遇到的放到map里
 * 并保存最大的长度
 * 如果遇到重复的字符，就去map里找到重复的key，然后将i指向value+1，这样就消除了这次重复
 * 比如abca，i指向0下标的a，如果遇到3下标的a，就把i向后移动一位，变成i指向b
 * 需要注意的是，i只往后移动，因此每次移动需要判断当前i是否比要移的目标值大，如果大就不移
 */
public class PThree无重复字符的最长子串{
//leetcode submit region begin(Prohibit modification and deletion)
class Solution {
    public int lengthOfLongestSubstring(String s) {
        int i= 0; // 最长字符的起始位置
        int max = 0;
        HashMap<Character,Integer> m = new HashMap<>();
        for (int j = 0; j < s.length(); j++) {
            char c = s.charAt(j);
            // 后面的条件考虑了abba的问题,遇到第4个a会出问题
            if(m.containsKey(c)&&i<m.get(c)+1){
                i=m.get(c)+1;
            }
            m.put(s.charAt(j),j);
            max= Math.max(j-i+1,max);
        }
        return max;
    }
}
//leetcode submit region end(Prohibit modification and deletion)

    public static void main(String[] args) { 
        Solution solution = new PThree无重复字符的最长子串().new Solution();
        int abcdeba = solution.lengthOfLongestSubstring("abcdeba");
        System.out.println(abcdeba);
    }
    @Test
    public void test(){
    }

}